1. Field of the Invention
The present invention is related to processing systems and networks, and more specifically to techniques for physical layout arrangement using a multi-dimensional bin-packing algorithm that tries combinations of remaining layout resources at each branch.
2. Description of Related Art
Software to solve multi-dimensional layout problems is used in layout of integrated circuit (IC) substrates and printed circuit boards (PCBs), as well as other physical space arrangements such as factory and server equipment layouts and warehouse/shipping storage applications.
A class of algorithms known as bin-packing algorithms can be used to determine efficient arrangement of objects, which correspond to circuit tracks, physical items, etc. within “bins”, which correspond to available layout partitions, e.g., circuit routing tracks, that can be used to complete an arrangement. Of particular interest are multi-dimensional bin-packing algorithms, since the mapping of objects to bins in the above problems is not a one-dimensional problem, since circuit width, via locations, availability of ground planes, distance from other tracks and other considerations for PCB or IC substrate layout may be orthogonal requirements, and for the warehousing/shipping case, the bin-packing algorithm may be a direct mapping to the multi-dimensional bin-packing problem.
While multi-dimensional bin-packing algorithms exist that can solve such problems, it is desirable to provide a method for arranging physical layouts that can efficiently perform such allocation without undue waste of resources.